package leetcode.code1373;

import leetcode.helper.tree.TreeNode;

public class Solution {

	final int yes = 1;
	final int no = 0;

	public int maxSumBST(TreeNode root) {
		int[] ans = f(root);
		// ans[0] = 1子树是，0子树不是；ans[1] 最大结果; ans[2] 子树最大值； ans[3] 子树最小值
		return Math.max(ans[1], 0);
	}

	private int[] f(TreeNode root) {
		if (root == null) {
			return new int[] { yes, 0, Integer.MIN_VALUE, Integer.MAX_VALUE };
		}
		int[] left = f(root.left);
		int[] right = f(root.right);
		int val = root.val;
		int cur = no;
		int ans = Math.max(left[1], right[1]);
		if (left[0] == yes && right[0] == yes && val > left[2] && val < right[3]) {
			cur = yes;
			ans = val + left[1] + right[1];
		}
		return new int[] { cur, ans, Math.max(val, Math.max(left[2], right[2])),
				Math.min(val, Math.min(left[3], right[3])) };
	}
}
